#include "abb.h"
#include "cr.h"
#include "cw.h"
#include <stdlib.h>
#include <stdio.h>

typedef struct Branch * Tree;
#define LEAF ((Tree) NULL)

/* FUNCIONES AUXILIARES NO EXPORTADAS EN EL HEADER */
Tree
tree_add(Tree t, Key k, Data d);

Tree
mkTree(Tree left, Key k, Data d, Tree right);

Tree
tree_del(Tree t, Key k);

Tree
max(Tree t);

Tree
tree_destroy(Tree t);

void
tree_print(Tree t);

void
tree_toCw(Tree t, cw c);
/* FIN FUNCIONES AUXILIARES */

struct sAbb
{
	int cant;
	Tree t;
};

struct Branch
{
	Tree l;
	Key k;
	Data d;
	Tree r;
};

Abb
abb_empty(void)
{
	Abb h;
	h = (Abb) malloc (sizeof(struct sAbb));
	
	if (h==NULL)
	{
		perror("No hay memoria en la función abb_empty");
		exit(EXIT_FAILURE);
	}
	h->cant = 0;
	h->t = NULL;

return h;
}

void
abb_add(Abb h, Key k, Data d)
{
	if (!(abb_exists(h,k)))
	{
		h->t = tree_add(h->t,k,d);
		h->cant += 1;
	}
}

Tree
tree_add(Tree t, Key k, Data d)
{
	if (t==LEAF)
		t = mkTree(LEAF,k,d,LEAF);
	else
	{
		if (!(key_eq(k,t->k)))
		{
			if (key_le(k,t->k))
				t->l = tree_add(t->l,k,d);
			else
				t->r = tree_add(t->r,k,d);
		}
	}
return t;
}

Tree
mkTree(Tree left, Key k, Data d, Tree right)
{
	Tree t;
	t = (Tree) malloc (sizeof(struct Branch));
	if (t==NULL)
	{
		perror("No hay memoria (funcion mkTree)");
		exit(EXIT_FAILURE);
	}
	else
	{
		t->l = left;
		t->k = key_clone(k);
		t->d = data_clone(d);
		t->r = right;
	}
return t;
}

Bool
abb_exists(Abb h, Key k)
{
	Bool b;
	Tree aux;
	
	aux=h->t;
	b = FALSE;
	
	while ((aux != LEAF) && (!b))
	{
		b = key_eq(k,aux->k);
		if (!b)
		{
			if(key_le(k,aux->k))
				aux = aux->l;
			else
				aux = aux->r;
		}
	}
	
return b;
}

Data
abb_search(Abb h, Key k)
{
	Data d;
	Tree aux;
	
	
	if (abb_exists(h,k))
	{	
		d = NULL;
		aux = h->t;
	
		while (aux!=NULL && d==NULL)
		{
			if(key_eq(k,aux->k))
				d = data_clone(aux->d);
			else
			{
				if(key_le(k,aux->k))
					aux = aux->l;
				else
					aux = aux->r;
			}
		}
	}
return d;
} 
	

void
abb_del(Abb h, Key k)
{
	if (abb_exists(h,k))
	{
		h->t = tree_del(h->t,k);
		h->cant -= 1;
	}
}

Tree
tree_del(Tree t, Key k)
{
	Tree minizq,aux;

	if (key_eq(t->k,k))
	{
		if (t->l == LEAF && t->r == LEAF)
			t = tree_destroy(t);
		else if (t->l == LEAF && t->r != LEAF)
		{
			aux = t;
			t = t->r;
			aux->r = LEAF;
			aux = tree_destroy(aux);
		}
		else if (t->l != LEAF)
		{
			minizq = max(t->l);
			t->k = key_destroy(t->k);
			t->d = data_destroy(t->d);
			t->k = key_clone(minizq->k);
			t->d = data_clone(minizq->d);
			t->l = tree_del(t->l,minizq->k);
		}
	}
	else if (key_le(k,t->k))
		t->l = tree_del(t->l,k);
	else
		t->r = tree_del(t->r,k);

return t;
}
	
Tree
max(Tree t)
{
	Tree m;
	m = t;
	if (m->r!=LEAF)
		m = max(t->r);
return m;
}


int
abb_length(Abb h)
{
	return h->cant;
}

Abb
abb_fromFile (char * nomfile)
{
	Key k;
	Data d;
	Tuple t;
	Abb h;
	cr c1;
	
	h = abb_empty();
	c1 = cr_create(nomfile);
	
	if (c1!=NULL)
	{
		cr_arr(c1);
		while (!cr_fin(c1))
		{
			t = cr_elec(c1);
			k = tuple_fst(t);
			d = tuple_snd(t);
			abb_add(h,k,d);
			cr_av(c1);
			t = tuple_destroy(t);
			k = key_destroy(k);
			d = data_destroy(d); /*las puedo borrar porq mkTree las clona*/
		}
	c1 = cr_destroy(c1);
	}
return h;
}

void
abb_toFile (char * nomfile, Abb h)
{
	cw c2;
	
	c2 = cw_create(nomfile);
	if (c2!=NULL)
	{
		cw_arr(c2);
		tree_toCw(h->t,c2);
		c2 = cw_destroy(c2);
	}
}

void
tree_toCw(Tree t, cw c)
{
	Tuple tt;
	Key k;
	Data d;
	
	if (t!=LEAF)
	{
		k = key_clone(t->k);
		d = data_clone(t->d);
		tt = tuple_fromKeyData(k,d);
		cw_ins(c,tt);		
		tt = tuple_destroy(tt);
		tree_toCw(t->l,c);
		tree_toCw(t->r,c);
	}
}	

Abb
abb_destroy(Abb h)
{
	if (h!=NULL)
	{
		h->t = tree_destroy(h->t);
		free(h);
		h = NULL;
	}
return h;
}

Tree
tree_destroy(Tree t)
{
	if (t!=LEAF)
	{
		t->k = key_destroy(t->k);
		t->d = data_destroy(t->d);
		t->l = tree_destroy(t->l);
		t->r = tree_destroy(t->r);
		free(t);
		t = NULL;
	}
return t;
}


void
abb_print(Abb h)
{
	if (h!=NULL)
		tree_print(h->t);
}

void
tree_print(Tree t)
{
	Key k;
	Data d;
	char * s1;
	char * s2;
	
	if (t!=NULL)
	{
		tree_print(t->l);
		s1 = (char *) calloc (key_maxLen(), sizeof(char));
		k = key_clone(t->k);
		d = data_clone(t->d);
		key_toString(k,s1);
		s2 = data_toString(d);
		printf("%s: %s\n",s1,s2);
		k = key_destroy(k);
		d = data_destroy(d);
		free(s2);
		free(s1);
		s2 = NULL;
		s1 = NULL;
		tree_print(t->r);
	}
}
